package com.wushijia.datastructure.list;

/**
 * 物理结构：单向链表
 * @author pc
 */
public class SinglyLinkedList<E> {

  private int size;

  private Node<E> head;

  private Node<E> tail;

  public SinglyLinkedList() {
    head = null;
    tail = null;
    size = 0;
  }

  static class Node<T> {

    private T data;
    private Node<T> next;

    public Node(T data) {
      this.data = data;
      this.next = null;
    }

    @Override
    public String toString() {
      return "Node{" +
          "data=" + data +
          ", next=" + next +
          '}';
    }
  }

  public void insert(int index, Node<E> node) {
    if (index <= 0) {
      //头部插入
      node.next = head;
      head = node;
      if (size == index) {
        tail = node;
      }
      size++;
    }
    if (index >= size) {
      //尾部插入
      tail.next = node;
      tail = node;
      size++;
    }
    int curr = 0;
    Node<E> currNode = head;
    while (currNode.next != null) {
      currNode = currNode.next;
      curr++;
      if (curr == index - 1) {
        Node<E> next = currNode.next;
        currNode.next = node;
        node.next = next;
        size++;
        break;
      }
    }
  }

//  public SinglyLinkedList reverseList(SinglyLinkedList old) {
//
//  }

  @Override
  public String toString() {
    return "LinkedList{" +
        "size=" + size +
        ", head=" + head +
        ", tail=" + tail +
        '}';
  }

  public static void main(String[] args) {
    SinglyLinkedList<String> linkedList = new SinglyLinkedList<>();
    Node<String> node = new Node<>("hello");
    Node<String> node2 = new Node<>("world");
    Node<String> node3 = new Node<>("gg");
    linkedList.insert(0, node);
    linkedList.insert(1, node2);
    linkedList.insert(4, node3);
    System.out.println(linkedList);
  }
}
